package baseclass.d_list;

import utils.ListNode;

/**
 * 找到链表的倒数第K个节点.
 * 方式1：翻转链表，然后再翻转回去。
 * 方式2：等价转换，倒数第K，等于正数第len + 1 - K
 * 方式3：准备fast,low。low在head，fast走到第k个。然后一起走，fast到了尾巴
 * low就到了倒数第k。
 * <p>
 * 注意代码的鲁棒性
 *
 * @date 2020/3/8 23:44
 */
public class Code12_FindKNodeFromTailInList_DeleteKNodeFromTail {
    public ListNode FindKthToTail1(ListNode head, int k) {
        if (head == null || k <= 0) return null;
        ListNode p = head;
        int len = 1;
        while (p.next != null) {
            len++;
            p = p.next;
        }
        if (k > len) return null;
        int target = len + 1 - k;
        p = head;
        while (--target != 0) {
            p = p.next;
        }
        return p;
    }

    public ListNode FindKthToTail2(ListNode head, int k) {
        if (head == null || k <= 0) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (--k != 0) {
            fast = fast.next;
            //链表长度小于k
            if (fast == null) return null;
        }
        //当fast走到tail,slow就走了倒数第k。所以是fast.next != null
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode FindKthToTail3(ListNode head, int k) {
        if (head == null || k <= 0) return null;
        ListNode newHead = reverseList(head);
        ListNode node = newHead;
        while (--k != 0) {
            node = node.next;
            //k > len
            if (node == null) return null;
        }
        reverseList(newHead);
        return node;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static void main(String[] args) {

    }
}
